\section{Search}
\label{search}

Search is the key component of Ringer.
Any document, once found, can be read.
It is the finding, in a distributed manor, which is the hard part.
One major goal of Ringer is not to be tied to any one search program. 
Instead, we designed Ringer to be a search framework, allowing many different algorithms to be easily implementable on top of the basic Ringer architecture.
Currently we explore two example approaches to search: human tagging and machine computed binary similarity.

\subsection{Tag Search}

The first search method we support is a tag based one.
Files are tagged by human users, using the extensible attribute component of the file's local inode.
The new tag is relayed to the client's MDS, which needs to update the index of tags.
This MDS attempts to find a MDS which ``owns" the tagged keyword, via a breadth-first search of its ancestors.
A parent MDS knows all of the keywords which its children own, and can respond to a keyword lookup request with the address of the owning child.
If no result comes back after a given timeout period, or if the owning MDS is down, the client's MDS notifies its parents that it has assumed ownership of the keyword.
If another MDS is found to be the owner, this MDS is sent the absolute Ringer path of the tagged file.
Note that there may be multiple owners for each keyword. 

This scheme is optimized for the assumption that clients are likely to re-use metadata tags, leading to fast lookup for commonly used tags. 
The number of owners is a function of how well connected the MDS parent relation graph is.
Note that there is no need to prepare a mapping of keywords to MDSs in advance.
There is also no reliance on any kind of central authority to arbitrate keywords. 
Associating keywords with specific owners allows us to prune the search space. 
There is no need to ask every MDS if they have a matching file: you only need to go up your list of ancestors high enough to identify which MDS owns the requested tags.

Human users (searchers) can query the system via a standalone program.
Searchers input a list of search keywords and a MDS via a command line interface.
The search program then contacts that MDS and relays the keyword list.
This MDS then looks up keyword owners, in the manor described above.
Again, if there is no owner, the MDS assumes ownership.
After collecting a list of owners, the MDS contacts the owners directly, asking for all files matching each keyword.
The responses are then collected into a single response and sent back to the issuing search program. 
The results are presented to the searcher as a list of Ringer file paths, grouped by the keywords satisfied.

An extension of tag based search would be a full text keyword search. 
In this form, all words in a file would be considered keywords, and indexed accordingly.
Beyond the communication overhead, we consider this extension unsatisfactory because our desire is for Ringer to work equally well with all data formats and languages, and not require specialized handling for any particular format.

\subsection{Similarity Search}

The other type of search implemented came about because we wanted a search which did not need any human input.

%$\Box $ Need more of a connection here, along with some background work.

Hash functions allow for a compact representation of a file, so that identical files can be quickly identified. 
With a \emph{similarity hash}, files which have similar content hash to similar values.
%This can be used for reducing redundancy or finding plagiarized copies of copy-writed content.

We integrated an existing similarity hashing function \footnote{Written by Caitlin Sadowski and Greg Levin, both graduate students at UCSC.} as a library in Ringer to create the similarity search.
This code works as follows: since the goal is binary similarity, the hashing function is initialized with a set of $n$ byte-strings to look for.
These byte-strings are static; the same strings are used on all files throughout the Ringer system.
In each file processed, the similarity hash counts the number of occurrences of each string.
These counts are turned into an $n$ dimensional vector.
Similarity is defined by the angle between vectors. 
As two files get closer to each other, we expect this angle to go to $0$.

In Ringer, similarity search uses a basic broadcast pattern.
When a file is added or edited, its similarity vector is computed and stored as part of its metadata.
Because we use a bounded set of strings to look for, this does not grow too large.
For search, a file and an epsilon are given to the search client.
The target file is hashed, and the hash value and the epsilon sent to a MDS. 
This MDS sends the search to its parents and children, and so on.
Any MDS which owns files with similarity vectors within an angle of epsilon to the searched for file's similarity vector are returned.
The results are recursively aggregated and returned, after a timeout period ends, as a list of Ringer paths to the original requesting search client.
%The broadcast search times out after a given period, which limits the scope of the search.

In practice, we do not separate out tagging and similarity search, instead giving the search client a mixed list of tags and file paths to hash.
%Any parameter which is a path to a file is passed to the similarity search, with the remainder assumed to be tags.
If a directory is given, all files in that directory are hashed separately.


